package Hot100.leetcode.editor.cn.code.二分;
//Java：寻找旋转排序数组中的最小值
public class FindMinimumInRotatedSortedArray{
    public static void main(String[] args) {
        Solution solution = new FindMinimumInRotatedSortedArray().new Solution();
    }
    //leetcode submit region begin(Prohibit modification and deletion)

    //设 x=nums[mid] 是现在二分取到的数。
    //
    //我们需要判断 x 和数组最小值的位置关系，谁在左边，谁在右边？
    //
    //把 x 与最后一个数 nums[n−1] 比大小：
    //
    //如果 x>nums[n−1]，那么可以推出以下结论：
    //nums 一定被分成左右两个递增段；
    //第一段的所有元素均大于第二段的所有元素；
    //x 在第一段。
    //最小值在第二段。
    //所以 x 一定在最小值的左边。
    //如果 x≤nums[n−1]，那么 x 一定在第二段。（或者 nums 就是递增数组，此时只有一段。）
    //x 要么是最小值，要么在最小值右边。
    //所以，只需要比较 x 和 nums[n−1] 的大小关系，就间接地知道了 x 和数组最小值的位置关系，从而不断地缩小数组最小值所在位置的范围，二分找到数组最小值。

    class Solution {
    public int findMin(int[] nums) {
        int left = 0;
        int right = nums.length -1;
        while(left < right){
            int mid = (left+right) >> 1;
            if(nums[mid] > nums[right]){
                left = mid+1;
            }else {
                right = mid;
            }
        }
        return nums[left];
    }
}
//leetcode submit region end(Prohibit modification and deletion)

}